// 6.33 假定用两个一维数组L[n+1]和R[n+1]作为有n个结点的二叉树的存储结构，L[i]和r[i]分别指示结点i（i=1,2,…,n）的左孩子和右孩子，0表示空。试写一个算法判别结点u是否为结点v的子孙。

// 6.34 同6.33题的条件。先由L和R建立一维数组T[n+1]，使T中第i（i=1,2,…,n）个分量指示结点i的双亲，然后写判别结点u是否为结点v的子孙的算法。

#include <stdio.h>
#include <stdlib.h>

bool fun_6_33(int L[], int R[], int u, int v)
{
    int i = 1;
    int stack[10];
    int top = -1;
    int visited[10] = {0};
    stack[++top] = u;
    visited[u] = 1;
    while (top >= 0)
    {
        int t = stack[top];
        if (L[t] == v || R[t] == v)
            return true;
        else
        {
            if (L[t] != 0 && !visited[L[t]])
            {
                stack[++top] = L[t];
                visited[L[t]] = 1;
            }
            else if (R[t] != 0 && !visited[R[t]])
            {
                stack[++top] = R[t];
                visited[R[t]] = 1;
            }
            else
            {
                top--;
            }
        }
    }
    return false;
}
// 第一问
void fun_6_34_1(int L[], int R[], int T[], int n)
{
    T[0] = -1;
    T[1] = 0;
    for (int i = 1; i < n; i++)
    {
        if (L[i])
            T[L[i]] = i;
        if (R[i])
            T[R[i]] = i;
    }
}
// 第二问
bool fun_6_34_2(int L[], int R[], int n, int u, int v)
{
    int T[10];
    fun_6_34_1(L, R, T, n);
    int t = v;
    while (T[t] != -1)
    {
        if (t == u)
            return true;
        t = T[t];
    }
    return false;
}
int main()
{
    /*******************code*******************/
    int L[] = {0, 0, 3, 0, 0, 0};
    int R[] = {0, 2, 4, 5, 0, 0};
    int u, v;
    u = 1;
    v = 5;
    if (fun_6_33(L, R, u, v))
        printf("YES");
    else
        printf("NO");

    if (fun_6_34_2(L, R, 6, u, v))
        printf("YES");
    else
        printf("NO");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
